LeetCode 199、二叉树的右视图

一、题目描述

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

二、题目解析

三、参考代码

1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 二叉树的右视图（ LeetCode 199 ）: https://leetcode-cn.com/problems/binary-tree-right-side-view/
class Solution {
    public List<Integer> rightSideView(TreeNode root) {

        // 设置一个数组用来存储二叉树的右视图结果
        // 题目要求存储的是节点的值，所以类型是 Integer
        List<Integer> list = new LinkedList<>();

        // 设置一个队列，用来保存二叉树每一层的节点
        Queue<TreeNode> que = new LinkedList<>();

        // 边界判断
        if (root == null) return list;
        
        // 首先，把二叉树的根节点加入到队列中
        que.add(root);

        // 观察队列是否为空
        while (!que.isEmpty()) {
            
            // 1、获取队列的长度
            int levelSize = que.size();

            // 2、通过一个循环，获取队列中每个节点的左右子树，把这些左右子树节点也添加到队列中
            for (int i = 0; i < levelSize; i++) {

                // 3、弹出队列的队首元素
                TreeNode node = que.poll();

                // 4、判断弹出的节点是否有左子树
                if (node.left != null) {
                    // 如果有左子树，把它加入到队列中
                    que.add(node.left);
                }

                // 5、判断弹出的节点是否有右子树
                if (node.right != null) {
                    // 如果有右子树，把它加入到队列中
                    que.add(node.right);
                }

                // 对于每一层的二叉树节点，我们是从左到右依次添加，所以末尾的节点的顺序是 levelSize - 1
                // 6、这个末尾的节点就是这一层中最右侧的节点 
                if (i == levelSize - 1) {
                    // 把最右侧的节点值加入到结果中
                    list.add(node.val);
                }
            }
        }
        // 返回结果
        return list;
    }
}

**2、**C++ 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 二叉树的右视图（ LeetCode 199 ）: https://leetcode-cn.com/problems/binary-tree-right-side-view/
class Solution {
public:
 vector<int> rightSideView(TreeNode* root) {

        // 设置一个数组用来存储二叉树的右视图结果
        // 题目要求存储的是节点的值，所以类型是 Integer
        vector<int> list;

        // 设置一个队列，用来保存二叉树每一层的节点
        queue<TreeNode*> que;

        // 边界判断
        if (root == NULL) return list;

        // 首先，把二叉树的根节点加入到队列中
        que.push(root);

        // 观察队列是否为空
        while (!que.empty()) {

            // 1、获取队列的长度
            int levelSize = que.size();

            // 2、通过一个循环，获取队列中每个节点的左右子树，把这些左右子树节点也添加到队列中
            for (int i = 0; i < levelSize; i++) {

                // 3、弹出队列的队首元素
                TreeNode* node = que.front();
    que.pop();

                // 4、判断弹出的节点是否有左子树
                if (node->left != NULL) {
                    // 如果有左子树，把它加入到队列中
                    que.push(node->left);
                }

                // 5、判断弹出的节点是否有右子树
                if (node->right != NULL) {
                    // 如果有右子树，把它加入到队列中
                    que.push(node->right);
                }

                // 对于每一层的二叉树节点，我们是从左到右依次添加，所以末尾的节点的顺序是 levelSize - 1
                // 6、这个末尾的节点就是这一层中最右侧的节点 
                if (i == levelSize - 1) {
                    // 把最右侧的节点值加入到结果中
                    list.push_back(node->val);
                }
            }
        }
        // 返回结果
        return list;
    
    }
};

3、Python 代码

登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者：程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 二叉树的右视图（ LeetCode 199 ）: https://leetcode-cn.com/problems/binary-tree-right-side-view/
class Solution:
    def rightSideView(self, root: TreeNode) -> List[int]:

        # 设置一个数组用来存储二叉树的右视图结果
        # 题目要求存储的是节点的值，所以类型是 Integer
        list = []

        # 设置一个队列，用来保存二叉树每一层的节点
        que = deque()

        # 边界判断
        if not root :
           return list

        # 首先，把二叉树的根节点加入到队列中
        que.append(root)

        # 观察队列是否为空
        while que:
            
            # 1、获取队列的长度
            levelSize = len(que)

            # 2、通过一个循环，获取队列中每个节点的左右子树，把这些左右子树节点也添加到队列中
            for i in range(levelSize):

                # 3、弹出队列的队首元素
                node = que.popleft()

                # 4、判断弹出的节点是否有左子树
                if node.left :
                    # 如果有左子树，把它加入到队列中
                    que.append(node.left)
                

                # 5、判断弹出的节点是否有右子树
                if node.right :
                    # 如果有右子树，把它加入到队列中
                    que.append(node.right)
                

                # 对于每一层的二叉树节点，我们是从左到右依次添加，所以末尾的节点的顺序是 levelSize - 1
                # 6、这个末尾的节点就是这一层中最右侧的节点 
                if i == levelSize - 1 :
                    # 把最右侧的节点值加入到结果中
                    list.append(node.val)
        
        # 返回结果
        return list